//给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。 
//
// 两个字符串 s 和 t 交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串： 
//
// 
// s = s1 + s2 + ... + sn 
// t = t1 + t2 + ... + tm 
// |n - m| <= 1 
// 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ... 
// 
//
// 提示：a + b 意味着字符串 a 和 b 连接。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：s1 = "", s2 = "", s3 = ""
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s1.length, s2.length <= 100 
// 0 <= s3.length <= 200 
// s1、s2、和 s3 都由小写英文字母组成 
// 
//
// 
//
// 
// 注意：本题与主站 97 题相同： https://leetcode-cn.com/problems/interleaving-string/ 
//
// Related Topics 字符串 动态规划 👍 70 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-03-31 23:23:35
 * @description LCR 096.交错字符串
 */
public class IY6buf{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 IY6buf fun=new IY6buf();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*
		 * 定义dp[i][j]为s1和s2前i,j个元素是否能组成s3前i+j个
		 * dp[i][j]=dp[i-1][j]&&s1[i-1]==s3[p] ||  dp[i][j-1]&&s2[j-1]==s3[p]
		 * */
	public boolean isInterleave1(String s1, String s2, String s3) {
		int m = s1.length();
		int n = s2.length();
		int t = s3.length();
		//和不等一定不行
		if(m+n!=t) return false;
		boolean [][] dp=new boolean[m+1][n+1];
		//两个空字符串，一定可以组成空字符串，也是边界条件
		dp[0][0]=true;
			/*
		* dp[i][0]表示只用s1的前i个匹配s3的前i个
		* dp[0][j]表示只用s2的前j个匹配s3的前j个
		* dp[i][j]有可能来自于s1，也可能是s2
		* dp[i][j] = dp[i-1][j] && (s1.charAt(i-1) == s3.charAt(i+j-1))。
		  dp[i][j] = dp[i][j-1] && (s2.charAt(j-1) == s3.charAt(i+j-1))。
		  两者或即可
		*
		* */
		for (int i = 0; i <=m; i++) {
			for (int j = 0; j <=n; j++) {
				int p=i+j-1;
				if(i>0){
					dp[i][j]=dp[i][j]||(dp[i-1][j]&&s3.charAt(p)==s1.charAt(i-1));
				}
				if(j>0){
					dp[i][j]=dp[i][j]||(dp[i][j-1]&&s3.charAt(p)==s2.charAt(j-1));
				}
			}
		}
		return dp[m][n];
	}
	//滚动数组，因为dp的第i行只和前一个有关
	public boolean isInterleave(String s1, String s2, String s3) {
		int m = s1.length();
		int n = s2.length();
		int t = s3.length();
		if(m+n!=t) return false;
		boolean [] dp=new boolean[n+1];
		dp[0]=true;
		for (int i = 0; i <=m; i++) {
			for (int j = 0; j <=n; j++) {
				int p=i+j-1;// s3当前索引
				if(i>0){
					//对s1原地滚动  是否可以从s1取
					dp[j]=(dp[j]&&s3.charAt(p)==s1.charAt(i-1));
				}
				if(j>0){
					//对s2数组滚动  是否可以从s2取，有可能dp[j]以及是true了，所以是或
					dp[j]=dp[j]||(dp[j-1]&&s3.charAt(p)==s2.charAt(j-1));
				}
			}
		}
		return dp[n];
	}


	public boolean isInterleave2(String S1, String S2, String S3) {
		int n = S1.length();
		int m = S2.length();
		if (n + m != S3.length()) {
			return false;
		}

		char[] s1 = S1.toCharArray();
		char[] s2 = S2.toCharArray();
		char[] s3 = S3.toCharArray();

		boolean[][] f = new boolean[n + 1][m + 1];
		f[0][0] = true;

		for (int j = 0; j < m; j++) {
			f[0][j + 1] = s2[j] == s3[j] && f[0][j];
		}
		for (int i = 0; i < n; i++) {
			f[i + 1][0] = s1[i] == s3[i] && f[i][0];
			for (int j = 0; j < m; j++) {
				f[i + 1][j + 1] = s1[i] == s3[i + j + 1] && f[i][j + 1] ||
						s2[j] == s3[i + j + 1] && f[i + 1][j];
			}
		}
		return f[n][m];
	}
	public boolean isInterleave3(String S1, String S2, String S3) {
		int n = S1.length();
		int m = S2.length();
		if (n + m != S3.length()) {
			return false;
		}

		char[] s1 = S1.toCharArray();
		char[] s2 = S2.toCharArray();
		char[] s3 = S3.toCharArray();

		boolean[] f = new boolean[m + 1];
		f[0] = true;
		for (int j = 0; j < m; j++) {
			f[j + 1] = f[j] && s2[j] == s3[j];
		}
		for (int i = 0; i < n; i++) {
			f[0] = f[0] && s1[i] == s3[i];
			for (int j = 0; j < m; j++) {
				f[j + 1] = f[j + 1] && s1[i] == s3[i + j + 1] ||
						f[j] && s2[j] == s3[i + j + 1];
			}
		}
		return f[m];
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
